﻿using System;
using System.Collections;
using System.Collections.Generic;
using Microsoft.Xna.Framework;
using Trippy.CollidableGameComponents;

namespace Trippy.Levels
{
    public class SpacePartitioner
    {
        private LinkedList<CollidableGameComponent>[][] grid;
        private float bucketSize;

        private float minX;
        private float minY;
        private float maxX;
        private float maxY;
        private float width;
        private float height;
        private int gridWidth;
        private int gridHeight;

        private LinkedList<LinkedList<CollidableGameComponent>> allocations = new LinkedList<LinkedList<CollidableGameComponent>>();

        /// <summary>
        /// 
        /// </summary>
        /// <param name="numObjects">Approximate number of items to be inserted</param>
        /// <param name="bucketSize">How many pixels on the grid </param>
        public SpacePartitioner(float minX, float minY, float maxX, float maxY, float bucketSize)
        {
            MakeGrid(minX, minY, maxX, maxY, bucketSize);
        }

        /// <summary>
        /// Recreates the grid. All items contained within are lost.
        /// </summary>
        public void MakeGrid(float minX, float minY, float maxX, float maxY, float bucketSize)
        {
            this.minX = minX;
            this.minY = minY;
            this.maxX = maxX;
            this.maxY = maxY;
            this.width = maxX - minX;
            this.height = maxY - minY;
            this.bucketSize = bucketSize;

            InitializeGrid();
        }

        private void InitializeGrid()
        {
            gridWidth = (int) Math.Ceiling(width / bucketSize + 10);
            gridHeight = (int) Math.Ceiling(this.height / bucketSize + 10);

            grid = new LinkedList<CollidableGameComponent>[gridWidth][];

            for (int i = 0; i < gridWidth; i++)
            {
                grid[i] = new LinkedList<CollidableGameComponent>[gridHeight];
            }
        }

        public void ClearGrid()
        {
            foreach (var cell in allocations)
            {
                cell.Clear();
            }

            allocations.Clear();
        }

        private void Add(int xPosition, int yPosition, CollidableGameComponent item)
        {


            if (grid[xPosition][yPosition] == null)
            {
                var newCell = new LinkedList<CollidableGameComponent>();
                grid[xPosition][yPosition] = newCell;

                allocations.AddLast(newCell);
            }
            // if there is a linked list, but its count is zero (it was cleared), add it to the allocations
            else if (grid[xPosition][yPosition].Count == 0)
            {
                allocations.AddLast(grid[xPosition][yPosition]);
            }
            // add the item
            grid[xPosition][yPosition].AddLast(item);
            
        }

        public void Add(CollidableGameComponent component)
        {
            int minY, minX, maxX, maxY;
        
            GetIntersectingRegions(component, out minY, out minX, out maxX, out maxY);

            for (int i = minX; i <= maxX; i++)
            {
                for (int j = minY; j <= maxY; j++)
                {
                    Add(i, j, component);
                }
            }
        }

        private void GetIntersectingRegions(CollidableGameComponent component, out int minY, out int minX, out int maxX, out int maxY)
        {

            minY = GetYBin(component.BoundingBox.Y);
            maxY = minY;
            minX = GetXBin(component.BoundingBox.X);
            maxX = minX;

            int currentX = GetXBin(component.BoundingBox.X);
            int currentY = GetYBin(component.BoundingBox.Y + component.BoundingBox.Height);

            if (currentX < minX) minX = currentX;
            if (currentY < minY) minY = currentY;
            if (currentX > maxX) maxX = currentX;
            if (currentY > maxY) maxY = currentY;

            currentX = GetXBin(component.BoundingBox.X + component.BoundingBox.Width);
            currentY = GetYBin(component.BoundingBox.Y);

            if (currentX < minX) minX = currentX;
            if (currentY < minY) minY = currentY;
            if (currentX > maxX) maxX = currentX;
            if (currentY > maxY) maxY = currentY;

            currentX = GetXBin(component.BoundingBox.X + component.BoundingBox.Width);
            currentY = GetYBin(component.BoundingBox.Y + component.BoundingBox.Height);

            if (currentX < minX) minX = currentX;
            if (currentY < minY) minY = currentY;
            if (currentX > maxX) maxX = currentX;
            if (currentY > maxY) maxY = currentY;
        }


        private int GetXBin(float x)
        {
            return (int)((x - minX) / bucketSize);
        }

        private int GetYBin(float y)
        {
            return (int)((y - minY) / bucketSize);
        }

        private void FindNeighbors(int xPosition, int yPosition, LinkedList<CollidableGameComponent> matches)
        {

            // since an object is added in every region that it intersects with, we only need to query our own region
            foreach (CollidableGameComponent c in grid[xPosition][yPosition])
            {
                matches.AddLast(c);
            }
        }

        public HashSet<CollidableGameComponent> FindNeighbors(CollidableGameComponent component)
        {
            int minY, minX, maxX, maxY;

            LinkedList<CollidableGameComponent> matches = new LinkedList<CollidableGameComponent>();

            GetIntersectingRegions(component, out minY, out minX, out maxX, out maxY);

            for (int i = minX; i <= maxX; i++)
            {
                for (int j = minY; j <= maxY; j++)
                {
                    FindNeighbors(i, j, matches);
                }
            }
        
            HashSet<CollidableGameComponent> matchSet = new HashSet<CollidableGameComponent>();

            foreach (CollidableGameComponent c in matches)
            {
                if (c != component) matchSet.Add(c);
            }

            return matchSet;
        }
    }
}
